namespace classifier_test
{

namespace high_order
{

class concept_clustering : public virtual virtual_object, private noncopyable
{
public:
	struct chunk
	{
		int concept;
	};
	struct concept
	{
		smart_ptr<validation_dataset> vdataset;
		smart_ptr<validation_classifier> vclassifier;
		double verror;
	};

	concept_clustering();
	concept_clustering(const concept_clustering& Val);
	virtual smart_ptr<concept_clustering> clone() const = 0;
	virtual void serialize(serializer& Serializer);
	virtual void initialize_options(command_line_options& Options) const;
	virtual void apply_arguments(const command_line_arguments& Args);

	virtual void set_base_classifier(classifier* Val);
	virtual void set_chunk_count(int Val) = 0;
	virtual void set_chunk(int I, smart_ptr<validation_dataset> VDataset, smart_ptr<validation_classifier> VClassifier, double VError) = 0;
	virtual void compute() = 0;
	virtual const chunk& get_chunk(int I) const = 0;
	virtual int get_concept_count() const = 0;
	virtual const concept& get_concept(int I) const = 0;
	double compute_validation_error() const;

protected:
	smart_ptr<classifier> BaseClassifier;
};

class high_order_concept_clustering : public concept_clustering
{
public:
	enum mode {chain_mode, graph_mode};

	high_order_concept_clustering();
	high_order_concept_clustering(const high_order_concept_clustering& Val);
	smart_ptr<concept_clustering> clone() const;

	void set_chunk_count(int Val);
	void set_chunk(int I, smart_ptr<validation_dataset> VDataset, smart_ptr<validation_classifier> VClassifier, double VError);
	void set_error_threshold(double Val);
	void set_mode(mode Val);
	void compute();
	const chunk& get_chunk(int I) const;
	int get_concept_count() const;
	const concept& get_concept(int I) const;

private:
	struct my_chunk : public chunk
	{
		smart_ptr<validation_dataset> vdataset;
		smart_ptr<validation_classifier> vclassifier;
	};
	struct node
	{
		bool useful; // does this merge result in smaller errors
		bool discarded; // is this node impossible to be a final cluster
		int left, right;
		smart_ptr<validation_dataset> vdataset; // available only when node is active
		smart_ptr<validation_classifier> vclassifier; // available only when !Discarded
		double errors, best_errors;
	};
	struct merge
	{
		double key;
		int left, right;
		smart_ptr<validation_classifier> vclassifier;
	};
	struct merge_worse
	{
		merge_worse(node* SetNodes = 0) : Nodes(SetNodes) {}
		bool operator()(const merge& A, const merge& B) const
		{
			if (A.key != B.key) return A.key > B.key;
			return
				Nodes[A.left].vdataset->size() + Nodes[A.right].vdataset->size() >
				Nodes[B.left].vdataset->size() + Nodes[B.right].vdataset->size();
		}
	private:
		node* Nodes;
	};
	typedef simple_heap<merge, merge_worse> merge_heap;
	typedef simple_graph<merge_heap::node*> merge_graph;

	mode Mode;
	double ErrThreshold;
	int Size;
	vector<my_chunk> Chunks;
	vector<node> Nodes;
	merge_graph Graph;
	merge_heap Heap;
	vector<concept_clustering::concept> Concepts;

	void init_nodes();
	void init_merges();
	void merge_nodes();
	void find_concepts();

	void train_node(node& Node, smart_ptr<validation_classifier> VClassifier);
	void discard_node(node& Node);
	void new_merge(int A, int B);
	void do_merge(const merge& Merge);
};

}

}
